C#和.Net框架

题目

题解

中心扩散

动态规划

动态规划的关键点：初始条件和状态转换方程。
设：s[l][r]表示字符串中下标L到R的位置
则有如下转态转换方程
s[l][r] = s[l+1][r-1] && (s[l] == s[r])
那初始状态呢
s[l][l] = ture
s[l][l+1] = (s[l] == s[l+1])

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>> v(s.size(),vector<bool>(s.size(),false));

        string res;

        for(int i = 0; i < v.size();++i)
        {
            for(int j = i; j < v.size();++j)
            {
                if(i == j)
                    v[i][j] = true;
                else if(j-i == 1)
                    v[i][j] = s[i] == s[j] ? true : false;
            }
        }

        //这里需要注意一点的是从后往前遍历，因为v[i][j] = v[i+1][j-1] && (s[i] == s[j]);会优先用到数组尾部的数据
        for(int i = v.size()-1; i >= 0;--i)
        {
            for(int j = i; j < v.size();++j)
            {
                if(j-i > 1)
                    v[i][j] = v[i+1][j-1] && (s[i] == s[j]);

                if(v[i][j] == true && j-i+1 > res.size())
                    res = s.substr(i,j-i+1);  
            }
        }

        return res;

    }
};